package com.example.algorithm.hot_topic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SlidingWindow {
    //    无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            if (dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }

    //    字符串所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        // 初始化数组统计字符串 p每个字符出现次数
        int[] cnt = new int[26];
        for(int i = 0; i < p.length(); i++){
            cnt[p.charAt(i) - 'a']++;
        }
        //滑动窗口左右边界
        int l = 0;
        for(int r = 0; r < s.length(); r++){
            // 更新当前窗口字符计数
            cnt[s.charAt(r) - 'a']--;
            // 从左侧收缩窗口，直到当前字符的计数在限定范围内
            while(cnt[s.charAt(r) - 'a'] < 0){
                cnt[s.charAt(l) - 'a']++;

                l++;
            }
            // 检查当前窗口大小是否等于字符串 p 的大小
            if(r - l + 1 == p.length()){
                ans.add(l);
            }
        }
        return ans;
    }
}
